package com.huawei.controller;

import java.util.*;

/**
 * description
 *
 * @author cwx1134046
 * @since 2023-01-30
 */
public class GetSkyline {
    public static List<List<Integer>> getSkyline(int[][] buildings) {
        PriorityQueue<int[]> queue = new PriorityQueue<>( (a,b) ->b[1]- a[1]);
        List<Integer> xList = new ArrayList<>();
        for (int[] building:buildings) {
            xList.add(building[0]);
            xList.add(building[1]);
        }
        Collections.sort(xList);
        List<List<Integer>> res = new ArrayList<>();
        int buildingIndex = 0;
        for (int x:xList){
            if(x == 2){
                System.out.println(5);
            }
            //高度入队列，横坐标为右边的x轴值
            while(buildingIndex <buildings.length && x >= buildings[buildingIndex][0] ){
                queue.offer(new int[]{ buildings[buildingIndex][1],buildings[buildingIndex][2]});
                buildingIndex++;
            }
            //当右边的x轴值 <=当前循环值时，出队列
            while(!queue.isEmpty() && queue.peek()[0] <= x) {
                queue.poll();
            }

            // y轴最大高度变化时，添加至返回
            int maxY = queue.isEmpty() ? 0:queue.peek()[1];
            if(res.size() == 0 || (maxY != res.get(res.size()-1).get(1))){
                res.add(Arrays.asList(x,maxY));
            }


        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        List<List<Integer>> skyline = getSkyline(arr);
        System.out.println(skyline);
    }
}
